#include <iostream>
using namespace std;
//  Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
// 2020.01.02
// 将两个链表代表的数求出来，然后加法运算，得到结果再转换为链表形式；
// 这种做法依赖于sum的大小，对变量类型有一定的要求，对于较大的数会溢出
class Solution1
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *temp;
        ListNode *out = new ListNode(0);
        int n1 = 0, n2 = 0, sum1 = 0, sum2 = 0, sum = 0;
        temp = l1;
        while (1)
        {
            if ((temp->next) == NULL)
            {
                sum1 = sum1 + ((temp->val) * pow(10, n1));
                temp = l2;
                break;
            }
            sum1 = sum1 + ((temp->val) * pow(10, n1));
            n1++;
            temp = temp->next;
        }

        while (1)
        {
            if ((temp->next) == NULL)
            {
                sum2 = sum2 + (temp->val) * pow(10, n2);
                temp = out;
                break;
            }
            sum2 = sum2 + (temp->val) * pow(10, n2);
            n2++;
            temp = temp->next;
        }
        sum = sum1 + sum2;
        cout << sum1 << endl
             << sum2 << endl
             << sum << endl;
        int front = 0;
        while (1)
        {
            if (sum < 10)
            {
                temp->val = sum;
                temp->next = NULL;
                break;
            }
            front = sum - (sum / 10) * 10;
            temp->val = front;
            //ListNode *newone = new ListNode(0);
            temp->next = new ListNode(0);
            temp = temp->next;
            sum = sum / 10;
        }
        return out;
    }
};
// 2020.01.02
// 不受限于变量类型，解决大数加法
class Solution2
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
         ListNode *out = l1;
        ListNode *l1_, *l2_;

        int jinwei = 0;
        while (l1 != NULL && l2 != NULL)
        {
            if ((l1->val + l2->val + jinwei) >= 10)
            {
                l1->val = (l1->val + l2->val + jinwei) % 10;
                jinwei = 1;
            }
            else
            {
                l1->val = (l1->val + l2->val + jinwei);
                jinwei = 0;
            }
            if (l1->next == NULL)
            {
                l1_ = l1;
                l2_ = l2;
            }
            if (l2->next == NULL)
            {
                l1_ = l1;
                l2_ = l2;
            }
            l1 = l1->next;
            l2 = l2->next;
        }

          if (l1 == NULL && l2 == NULL)
        {
            if (jinwei == 1)
            {
                l1_->next = new ListNode(1);
            }
            return out;
        }

        if (l1 == NULL && l2 != NULL)
        {
            l1_->next = new ListNode(0);
            l1 = l1_->next;
            while (l2 != NULL)
            {
                if ((l2->val + jinwei) >= 10)
                {
                    l1->val = 0;
                    jinwei = 1;
                }
                else
                {
                    l1->val = (l2->val + jinwei);
                    jinwei = 0;
                }
                l2 = l2->next;
                if (l2 != NULL)
                {
                    l1->next = new ListNode(0);
                    l1 = l1->next;
                }
                else
                {
                    if (jinwei == 1)
                        l1->next = new ListNode(1);
                }
            }
            return out;
        }

        if (l1 != NULL && l2 == NULL)
        {
            while (l1 != NULL)
            {
                if ((l1->val + jinwei) >= 10)
                {
                    l1->val = 0;
                    jinwei = 1;
                }
                else
                {
                    l1->val = (l1->val + jinwei);
                    jinwei = 0;
                }
                if (l1->next == NULL)
                {}
                    if (jinwei == 1)
                        l1->next = new ListNode(1);
                        return out;
                }
                l1 = l1->next;
            }
           // return out;
        }
        return  0;
    }
};
